#_*_coding:utf-8_*_
'''
509 斐波那契数列
题目：
    斐波那契数列，通常用 F(n) 表示，形成的序列称为斐波那契数列，该数列由
    0和1开始，后面的每一项都是前面两项数字的和，也就是：
        F(0) = 0  F(1) = 1
        F(N) = F(N-1) + F(N-2)  ，其中 N > 1
    给定N，计算 F(N)

示例 1：
    输入：2
    输出：1
    解释：F(2) = F(1) + F(0) = 1 + 0 = 1.

示例 2：
    输入：3
    输出：2
    解释：F(3) = F(2) + F(1) = 1 + 1 = 2.

示例 3：
    输入：4
    输出：3
    解释：F(4) = F(3) + F(2) = 2 + 1 = 3.

注意：
    0<=N<=30
'''
class Solution:
    def fib1(self, N: int) -> int:
        '''
            方法1：递归
            我们直接通过题目给定的公式，进行递归调用自身即可得出结果
            如果怕溢出，可以加一个判断，判断N是否大于30

            复杂度分析：
                时间复杂度：O(2^N)，这是计算斐波那契数列最慢的方法，因为它需要指数的时间
                空间复杂度：O(N)，在堆栈中我们需要与N成正比的空间大小。该堆栈跟踪fib(N)的
                            函数调用，随着堆栈的不断增长，如果没有足够的内存会导致内存溢出

            所以不推荐使用
        '''
        if N <= 1:
            return N
        return self.fib1(N-1) + self.fib1(N-2)


    def fib2(self, N: int) -> int:
        '''
            改进递归：
            我们也看到了递归存在大量的重复计算，所以我们记下来每次计算的结果
            这样就不会存在重复计算了。

            复杂度分析：
                时间复杂度：O(N)
                空间复杂度：O(N)
        '''
        if N <= 1:
            return N
        dp = [0] * (N+1)
        dp[0], dp[1] = 0, 1
        for i in range(2, N+1):
            dp[i] = dp[i-1] + dp[i-2]
        return dp[N]


    def fib3(self, N: int) -> int:
        '''
            自底向上迭代
                若N<=1，则返回N
                若N>1，则可以使用迭代的方法，我们存储两个值，不停的迭代即可

            复杂度分析：
                时间复杂度：O(N)
                空间复杂度：O(1)
        '''
        if N <= 1:
            return N
        a, b = 0, 1
        for i in range(2, N+1):
            a, b = b, a+b
        return b

    def fib4(self, N: int) -> int:
        '''
            使用黄金分割比公式

            复杂度分析：
                时间复杂度：O(1)
                空间复杂度：O(1)
        '''
        golden_ratio = (1 + 5**0.5)/2
        return int(golden_ratio ** N+1)/5**0.5
